1. Field of the Invention
This invention relates to the field of data processing generally, particularly to performing fast searches in data having many large data objects to find matches to an unknown similar large data object. It has particular application to authentication utilizing biometric data and more specifically the method and process of biometric database searching.
2. Background
A significant problem facing biometric identification using a large population is the processing time required to perform a full comparison on the entire population to a presenting person, so as to identify that person. Even when the database processing is optimized and the data is available before the comparison, the biometric comparison operation becomes a timing bottleneck that slows the identification process on large populations to such a degree as to make real time use of such searches unavailable. One way to decrease the time required for biometric identification of an individual is to decrease the population against which a comparison must be performed. One potential solution is to use a mechanism to narrow the potential match population must be used to restrict the set of biometric templates from the overall population of templates needing to be compared to the collected biometric data, or rather, the collected biometric data in a templatized form.
Currently, there are a few mechanisms proposed to do this. One method of reducing the population of templates used for fingerprint comparison is based on comparing 5 predetermined characteristic data points of a fingerprint. Using a comparison of these 5 data points in the collected biometric and comparing it to the same five data points in the potential population of templates reduces the amount of digit-wise compares that have to be accomplished. Only on the population sample's templates that match on the 5 data points of the captured biometric can be relevant, so only on those that match is a full biometric comparison performed.
This method has several disadvantages. First, the solution has only been demonstrated for fingerprint identification data sets and may therefore not be transferable to other methods of biometric identification including facial and iris pattern recognition data sets. Second, the solution has been fixed to a specific database, e.g. Oracle RDBMS, to provide fast database indexing with multiple keys for searching. Third, the accuracy of the method is affected as the biometric data retrieved changes. Biometric data collected from a given individual can change over time for many reasons including age, trauma, and so on.
We have discovered that by using an algorithm to generate a small, derivative key from a template, a database would be able to create an index capable of identifying one or more candidate records to examine in detail. Rather than comparing the unknown biometric to, say, 100,000,000 records, a system would then be able to identify perhaps 10,000 possible matches for detailed examination, cutting processing time from hours to less than a second.
A real world example for how this could be applied would be the US VISIT program which calls for passing a person through a lane (as in an immigration lane) in a matter of a few seconds or less while comparing that person to a watch list of dangerous or undesirable people. Current state of the art will not allow this watch list to exceed 12,000 people (using fingerprint data for example), as current technology limits biometric searches to about 20,000 records per second (20,000×6 seconds=120,000 records; 120,000÷10 fingers=12,000 people).